백준 11375번

오늘 풀어본 문제는 백준의 11375번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 7

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

강호네 회사에는 직원이 $N$ 명이 있고, 해야할 일이 $M$ 개가 있다. 직원은 $1$ 번부터 $N$ 번까지 번호가 매겨져 있고, 일은 $1$ 번부터 $M$ 번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, $M$ 개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 $N$ 과 일의 개수 $M$ 이 주어진다. $(1 \leq N, M \leq 1,000)$

둘째 줄부터 $N$ 개의 줄의 $i$ 번째 줄에는 $i$ 번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력

첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

풀이과정

1번째 시도

이 문제는 ‘이분 매칭’ 문제이다. 이분 매칭이 무엇인지 간단하게 설명하자면, 이분 그래프에서 간선들이 한쪽 그룹에서 다른 그룹으로만 향하는 그래프의 최대 유량을 구하는 것이다.

문제를 읽어보면 알겠지만, 할 수 있는 일의 최대 개수를 알아야 하고, 직원과 일로 그룹을 나눌 수 있으며, 간선의 방향을 직원에서 일로 가도록 이분 그래프를 만들 수 있다. 여기서 최대 유량을 구하면 그게 곧 할 수 있는 일의 최대 개수가 되는 것이다.

문제를 풀기 위해서 Ford-Fulkerson, Edmond-Karp 알고리즘을 사용할 수도 있겠지만, 비교적 간단한 방법인 DFS를 이용하여 해결하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

bool visited[1002] = { 0, };

int assignedWork[1002] = { 0, };
int getWorker[1002] = { 0, };

vector<int> graph[1002];

bool match(int worker);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, answer = 0;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		int numberOfWorks;
		cin >> numberOfWorks;

		while (numberOfWorks--) {
			int workNumber;
			cin >> workNumber;
			
			graph[i].emplace_back(workNumber + N);
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int i = 1; i <= N; i++) {
			visited[i] = false;
		}
		answer += match(i);
	}

	cout << answer;

	return 0;
}

bool match(int worker) {
	if (visited[worker] == false) {
		visited[worker] = true;
		for (auto possibleWork : graph[worker]) {
			if (getWorker[possibleWork] == 0 || match(getWorker[possibleWork])) {
				assignedWork[worker] = possibleWork;
				getWorker[possibleWork] = worker;
				return 1;
			}
		}
	}
	return 0;
}

실행 결과 ‘런타임 에러 (OutOfBounds)’ 가 발생하였다.

2번째 시도

이런 문제가 발생한 이유는 처음에 그래프를 설정하는 과정에서 정점의 개수의 최댓값을 $N + M$ 의 최댓값이 아니라 $N$의 최대값으로 설정했기 때문이다.

각 배열에서 정점의 개수의 최댓값을 바꿔줄 수도 있었겠지만, 정점의 번호가 겹쳐도 간선의 방향이 다른 그룹으로만 향하기 때문에 문제가 발생하지 않을 것이라고 생각하여 그래프를 구성하는 과정에서 일 그룹에 해당하는 정점의 번호를 그냥 일의 번호로 설정하는 방식으로 수정하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

bool visited[1002] = { 0, };

int assignedWork[1002] = { 0, };
int getWorker[1002] = { 0, };

vector<int> graph[1002];

bool match(int worker);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, answer = 0;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		int numberOfWorks;
		cin >> numberOfWorks;

		while (numberOfWorks--) {
			int workNumber;
			cin >> workNumber;
			
			graph[i].emplace_back(workNumber);
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int i = 1; i <= N; i++) {
			visited[i] = false;
		}
		answer += match(i);
	}

	cout << answer;

	return 0;
}

bool match(int worker) {
	if (visited[worker] == false) {
		visited[worker] = true;
		for (auto possibleWork : graph[worker]) {
			if (getWorker[possibleWork] == 0 || match(getWorker[possibleWork])) {
				assignedWork[worker] = possibleWork;
				getWorker[possibleWork] = worker;
				return 1;
			}
		}
	}
	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

문제의 CLASS 를 보고 예상했겠지만, 세미나의 연습 문제로 나온 문제이다. 세미나에서 배우는 내용들이 어려운만큼, 연습 문제도 어렵고, 그렇다 보니 CLASS도 높은 문제들이 많은 것 같다.

더 쉬운 세미나를 지난 학기에 듣지 않은 것은 아니지만, 이렇게 본격적으로 PS를 시작하게 된 것은 최근이다. 그래서 세미나의 진도와 내 배경지식의 수준의 갭이 종종 많이 발생한다. 그걸 채우기 위해 CLASS 2 부터 계속 달려오고 있는 것이다. CLASS 4도 후딱 해치우고 5까지는 끝내둬야 진도를 따라잡을 수 있을 것 같다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/11375

← Previous Post Next Post →